﻿#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;
/*------------------------------------------------------------------
		* 主题：图算法
		* 作者：周伯涵
		* 时间：2022.5.1
		* 描述：函数输入为基类的实例化，派生类增强代码可读性
					 _test()为测试代码具备输入输出结果
   ------------------------------------------------------------------*/

const float inf = float(1e8);//不可达的最远距离
bool operator==(vector<float>a, vector<float>b) {
	if (a.size() != b.size())return 0;
	for (int i = 0; i < a.size(); i++)
		if (a[i] != b[i])return 0;
	return 1;
}

//输出
template<class T>
ostream& operator<<(ostream& o, vector<T>a) {
	for (int i = 0; i < a.size(); i++)o << a[i] << "\t";
	return o << "\n";
}
template<class T>
ostream& operator<<(ostream& o, vector<vector<T>>a) {
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < a[0].size(); j++) {
			o << a[i][j] << "\t";
		}
		o << "\n";
	}
	return o;
}

//定义图结构
struct Edge {
	int from, to;
	float distance;
	friend bool operator<(Edge x, Edge y) {//自定义结构体的优先级由小于号确定
		return x.distance < y.distance;
	}
	friend ostream& operator<<(ostream& o, Edge e) {
		//输出边信息
		o << "(" << e.from << "," << e.to << "): " << e.distance;
		return o;
	}
};
class UndirectedGraph {
protected:
	int n;//number of vertices
	vector<vector<int>>A;//Adjacency Matrix
	vector<vector<float>>W;//Distance Matrix
public:
	UndirectedGraph(int num, vector<pair<int, int>>g) : //邻接矩阵、入度出度初始化(节点编号从0到n-1)
		n(num),
		A(n, vector<int>(n, 0)) {//默认没有自环，对角线全0
		for (auto each : g)
			A[each.first][each.second] = A[each.second][each.first] = 1;//双向
	}
	UndirectedGraph(int num, vector<Edge>e) :
		n(num),
		W(n, vector<float>(n, inf)) {
		for (auto each : e)
			W[each.from][each.to] = W[each.to][each.from] = each.distance;//无向图距离矩阵是对称阵
		for (int i = 0; i < n; i++)W[i][i] = 0;//W_{ii}=0
	}
	friend ostream& operator<<(ostream& o, UndirectedGraph g) {
		o << "-----------------------------------------------------------\n";
		//输出邻接矩阵
		o << "Adjacency Matrix: \n" << g.A;
		//输出距离矩阵
		o << "Distance Matrix: \n" << g.W;
		o << "-----------------------------------------------------------\n";
		return o;
	}
};
class DirectedGraph {
protected:
	int n;//number of vertices
	vector<int>indegree, outdegree;//Indegree
	vector<vector<int>>A;//Adjacency Matrix
	vector<vector<float>>W;//Distance Matrix
public:
	DirectedGraph(int num, vector<pair<int, int>>g) : //邻接矩阵、入度出度初始化(节点编号从0到n-1)
		n(num),
		A(n, vector<int>(n, 0)),//默认没有自环，对角线全0
		indegree(n, 0),
		outdegree(n, 0) {
		for (auto each : g) {
			A[each.first][each.second]++;//pair中second指向first
			indegree[each.second] ++;
			outdegree[each.first] ++;
		}
	}
	DirectedGraph(int num, vector<Edge>e) :
		n(num),
		W(n, vector<float>(n, inf)) {
		for (auto each : e)
			W[each.from][each.to] = each.distance;
		for (int i = 0; i < n; i++)W[i][i] = 0;//W_{ii}=0
	}
	friend ostream& operator<<(ostream& o, DirectedGraph g) {
		o << "-----------------------------------------------------------\n";
		//输出邻接矩阵
		o << "Adjacency Matrix: \n" << g.A;
		//输出距离矩阵
		o << "Distance Matrix: \n" << g.W;
		//输出入度
		o << "Indegree: " << g.indegree;
		//输出出度
		o << "Outdegree: " << g.outdegree;
		o << "-----------------------------------------------------------\n";
		return o;
	}
};

//遍历
class Traversal : public UndirectedGraph {
public:
	Traversal(int num, vector<pair<int, int>>g) : UndirectedGraph(num, g) {}
	void _dfs(int v, vector<bool>& vis, vector<int>& res) {
		vis[v] = 1;
		res.emplace_back(v);
		for (int i = 0; i < n; i++)
			if (!vis[i] && A[v][i])
				_dfs(i, vis, res);
	}
	vector<int>DFS() {
		/*----------------------------------------------------------------------------------------------
		* 输入：无向图邻接矩阵
		* 输出：深度优先节点遍历序列
		辅助数组vis记录节点是否访问，对连通图子函数_dfs(v)即可输出所有节点的序列，非连通图有
		多个连通分支需要外层循环才能遍历完
		----------------------------------------------------------------------------------------------*/
		vector<int>res;
		vector<bool>vis(n, 0);//初始所有节点都没有被访问
		for (int v = 0; v < n; v++)
			if (!vis[v]) {//开启一个连通分支
				_dfs(v, vis, res);
			}
		return res;
	}
	vector<int>BFS() {
		/*----------------------------------------------------------------------------------------------
		* 输入：无向图邻接矩阵
		* 输出：广度优先节点遍历序列
		辅助数组vis记录节点是否访问，队列实现“层序遍历”，非连通图多个连通分支需要额外循环
		----------------------------------------------------------------------------------------------*/
		vector<int>res;
		vector<bool>vis(n, false);//初始所有节点都没有被访问
		queue<int>Q;//可以是node类型的队列包含点权信息
		for (int v = 0; v < n; v++)
			if (!vis[v]) {//开启一个连通分支
				vis[v] = 1;
				Q.push(v);//原则：能push到队列中的都是访问过的节点
				while (Q.size()) {
					auto top = Q.front();
					Q.pop();
					res.emplace_back(top);
					for (int i = 0; i < n; i++)
						if (!vis[i] && A[top][i]) {
							vis[i] = 1;
							Q.push(i);
						}
				}
			}
		return res;
	}
	static void _test(string method) {
		Traversal
			g(5, { {0,1},{0,2},{1,3},{1,4},{2,3} }); //深度优先搜索结果：0     1       3       2       4
																 //广度优先搜索结果：0     1       2       3       4
		cout << g;
		if (method == "dfs")
			cout << "深度优先搜索结果：" << g.DFS();
		if (method == "bfs")
			cout << "广度优先搜索结果：" << g.BFS();
	}
};

//最小生成树
class MST :public UndirectedGraph {//Minimum Spanning Tree
	vector<Edge>edges;
public:
	MST(int num, vector<Edge>e) : UndirectedGraph(num, e), edges(e) {}
	//Prim算法：针对顶点，对于稠密图(边数非常多的情况)更好；
	//Kruskal算法：针对边，对于稀疏图(边数少)时更好。
	pair<vector<Edge>, float>Prim() {
		/*------------------------------------------------------------------------------------------------
			* 输入：无向图距离矩阵
			* 输出：组成生成树的边，最短距离和
			Prim算法最小生成树步骤：
			1.随机选取无向图中某个节点初始化集合A，剩余节点为集合~A
			2.不断选取两集合中截集/割/桥中的最短边将节点从集合~A放入集合A直至A为全集~A为空集
			时间复杂度O(V^2)
			----------------------------------------------------------------------------------------------*/
			//返回值
		float cost = 0.0;//最小生成树边权和
		vector<Edge>res;//组成最小生成树的边

		int cur = 0;//默认从节点0开始
		//以下两个数组可以绑定为(value,index)结构体
		vector<float>curmincost(W[0]);//集合A中的点cur到集合~A中的点的最短距离，-1表示已访问
		vector<int>minfrom(n, 0);//当前最短距离来自节点编号，curmincost下标表示终点
		curmincost[cur] = -1;//初始点0已访问
		for (int i = 1; i < n; i++) {//最小生成树由n-1条边组成
			//part1: 找到A中cur到~A间的最短距离以及对应~A中的节点P
			float mindis = inf;
			for (int j = 0; j < n; j++)
				if (curmincost[j] < mindis && curmincost[j] != -1) {
					mindis = curmincost[j];
					cur = j;
				}
			//~A中的节点P加入A中，此时A中的cur就是节点P，将结果加入返回值
			cost += mindis;
			res.push_back({ minfrom[cur],cur,mindis });
			curmincost[cur] = -1;//已访问
			//part2: 更新：A中cur（节点P）到~A间的最短距离和节点索引
			for (int j = 0; j < n; j++)
				if (W[cur][j] < curmincost[j]) {//节点P能够更新集合~A中的某节点Q
					curmincost[j] = W[cur][j];
					minfrom[j] = cur;
				}
		}
		return { res,cost };
	}
	pair<vector<Edge>, float>Kruskal() {
		/*------------------------------------------------------------------------------------------------
			* 输入：无向图边集合
			* 输出：组成生成树的边，最短距离和
			Kruskal算法最小生成树步骤：
			将边数组根据权重升序排序，在不构成环的条件下从小到大取出n-1条边即构成最小生成树
			时间复杂度O(ElogE)，空间复杂度O(V+E)
			----------------------------------------------------------------------------------------------*/
			//返回值
		float cost = 0.0;//最小生成树边权和
		vector<Edge>res;//组成最小生成树的边
		//定义并查集
		class DisjointSet//并查集检查图中是否有环
		{
			vector<int>disjointset;//disjointset[i]表示i这个节点的父亲是谁
			vector<int>depth;
			int n;
		public:
			DisjointSet(int num) :n(num), depth(num, 0)
			{
				for (int i = 0; i < n; i++)
					disjointset.emplace_back(i);//初始每个子集互斥
			}
			int FindRoot(int p)
			{
				while (disjointset[p] != p)p = disjointset[p];
				return p;
			}
			bool Union(int x, int y)//0 有环   1  无环
			{
				int x_root = FindRoot(x);
				int y_root = FindRoot(y);
				if (x_root == y_root)return 0;
				//两个已经在同一集合的元素构建联系时发现根相同，说明出现环
				else
				{
					if (depth[x] < depth[y])disjointset[x_root] = y_root;
					else if (depth[x] > depth[y])disjointset[y_root] = x_root;
					else if (depth[x] == depth[y])//避免形成一条长链
					{
						disjointset[y_root] = x_root;//set[x_root] = y_root;也行，后面根改成rank[y_root]++;
						depth[x_root]++;//根的深度+1
					}
					return 1;
				}
			}
			void PrintSet()
			{
				for (int i = 0; i < n; i++)cout << disjointset[i] << " "; cout << endl;
			}
			void PrintDepth()
			{
				for (int i = 0; i < n; i++)cout << depth[i] << " "; cout << endl;
			}
		}set(n);
		//边数组升序排序
		sort(edges.begin(), edges.end());
		//从小到大取出n-1条边(保证无环)
		for (auto edge : edges) {
			if (set.Union(edge.from, edge.to)) {//无环则加入。有环则跳过
				res.push_back(edge);
				cost += edge.distance;
			}
			if (res.size() == n - 1)break;
		}
		return { res,cost };
	}
	static void _test(string method) {
		MST g1(6,
			{
				{0,1,6},
				{0,2,1},
				{0,3,5},
				{1,2,5},
				{1,4,3},
				{2,3,5},
				{2,4,6},
				{2,5,4},
				{3,5,2},
				{4,5,6},
			});
		//【Prim】
		//中间curmincost变化：
		// {m, 6, 1, 5, m, m}
		// {m, 5, m, 5, 6, 4}
		// {m, 5, m, 2, 6, m}
		// {m, 5, m, m, 6, m}
		// {m, m, m, m, 3, m}
		// {m, m, m, m, m, m}
		//输出：
		//组成生成树的边：(0, 2) : 1        (2, 5) : 4        (5, 3) : 2        (2, 1) : 5        (1, 4) : 3
		//最短距离和：15
		//【Kruskal】
		//组成生成树的边：(0,2): 1        (3,5): 2        (1,4): 3        (2,5): 4        (1,2): 5
		//最短距离和：15
		cout << g1;
		pair<vector<Edge>, float> res;
		if (method == "prim")
			res = g1.Prim();
		if (method == "kruskal")
			res = g1.Kruskal();
		cout << "组成生成树的边：" << res.first;
		cout << "最短距离和：" << res.second;
	}
};

//最短距离
class MinDist :public DirectedGraph {
	vector<Edge>edges;
public:
	MinDist(int num, vector<Edge>e) :DirectedGraph(num, e), edges(e) {}
	pair<vector<float>, vector<int>>Dijkstra() {
		/*----------------------------------------------------------------------------------------------
		* 输入：有向图距离矩阵
		* 输出：初始节点0到每个节点的最短距离，最短路径索引表
		Dijkstra算法步骤：
		1. 起始点0加入集合A，其余节点加入集合~A，以节点0到其他节点的距离初始化mindistance
			（不可达则∞），parent均初始化为节点0（不可达则-1）
		2. ~A中最短距离mindistance[j]则为节点0到节点j的最短距离，将节点j加入集合A，用节点j
			松弛更新mindistance
		3. 不断重复2直至所有节点均在集合A中
		时间复杂度O(V^2)
		----------------------------------------------------------------------------------------------*/
		//初始化
		vector<float>mindistance(W[0]);//始终维护节点0到其他节点当前的最短距离
		vector<int>parent;
		for (int i = 0; i < n; i++)
			parent.emplace_back(W[0][i] == inf ? -1 : 0);//节点0可达的点的来源都是节点0
		vector<bool>flag(n, 0);
		flag[0] = 1;//节点0在集合A中,flag=1的点既不参与索引也不参与更新
		//循环n-1次
		for (int i = 1; i < n; i++) {
			//找到~A中最小的mindistance
			float mindist = inf;
			int minindex = 0;
			for (int j = 1; j < n; j++)
				if (!flag[j] && mindistance[j] < mindist) {
					mindist = mindistance[j];
					minindex = j;
				}
			flag[minindex] = 1;
			//用节点j进行松弛
			for (int k = 1; k < n; k++)
				if (!flag[k] && mindist + W[minindex][k] < mindistance[k]) {
					mindistance[k] = mindist + W[minindex][k];
					parent[k] = minindex;
				}
		}
		return { mindistance,parent };
	}
	vector<float>Bellman_Ford(int k=inf) {
		/*----------------------------------------------------------------------------------------------
		* 输入：有向图边集合
		* 输出：初始节点0到每个节点k次更新下的最短距离（负环的存在最短距离可以达到-∞）
		Bellman-Ford算法步骤：
		循环k次（相当于尝试了所有1次松弛~k次松弛的情况，对于无负环的图最多循环V-1次）
		每次循环遍历所有边松弛更新，若收敛则停止
		时间复杂度O(VE)明显高于Dijkstra，但适用于存在负环的图！
		----------------------------------------------------------------------------------------------*/
		vector<float>res(n,inf);
		res[0] = 0;//初始化
		for (int i = 0; i < k; i++) {
			vector<float>res_(res);//迭代前先备份
			for (auto e : edges)
				res[e.to] = min(res[e.to], res[e.from] + e.distance);
			if (res == res_)
				break;
		}
		return res;
	}
	vector<vector<float>>Floyd() {
		/*----------------------------------------------------------------------------------------------
		* 输入：有向图距离矩阵
		* 输出：任意两点之间的最短距离
		Floyd算法步骤：
		动态规划，对于每一对顶点(u,v)若存在中转顶点 w 使得 dis(u,w)+dis(w,v)<dis(u,v) 则更新
		----------------------------------------------------------------------------------------------*/
		vector<vector<float>>res(W);
		//最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，总而言之：从i号顶点到j号顶点只经过前k号点的最短路程
		for (int k = 0; k < n; k++)
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					if (res[i][k] + res[k][j] < res[i][j])
						res[i][j] = res[i][k] + res[k][j];
		return res;
	}
	static void _test_Dijkstra() {
		MinDist g(5,
			{
				{0,1,10},
				{0,3,30},
				{0,4,100},
				{1,2,50},
				{2,4,10},
				{3,2,20},
				{3,4,60},
			});
		cout << g;
		pair<vector<float>, vector<int>>res = g.Dijkstra();
		cout << "从节点0到各节点最短距离：" << res.first;//[0,10,50,30,60]
		cout << "路径索引表：" << res.second;//[0,0,3,0,2]
	}
	static void _test_Bellman_Ford() {
		MinDist g(5,
			{
				{0,1,10},
				{0,3,30},
				{0,4,100},
				{1,2,50},
				{2,4,10},
				{3,2,20},
				{3,4,60},
			});
		cout << g;
		vector<float>res = g.Bellman_Ford();
		cout << "从节点0到各节点最短距离：" << res;//[0,10,50,30,60]
	}
	static void _test_Floyd() {
		MinDist g(5,
			{
				{0,1,10},
				{0,3,30},
				{0,4,100},
				{1,2,50},
				{2,4,10},
				{3,2,20},
				{3,4,60},
			});
		/*
		最短距离矩阵：
		0       10      50      30      60
		1e+08   0       50      1e+08   60
		1e+08   1e+08   0       1e+08   10
		1e+08   1e+08   20      0       30
		1e+08   1e+08   1e+08   1e+08   0
		*/
		cout << g;
		vector<vector<float>>res = g.Floyd();
		cout << "最短距离矩阵：\n" << res;
	}
};

//拓扑排序
class ToplogicalSort :public DirectedGraph {
public:
	ToplogicalSort(int num, vector<pair<int, int>>g) :DirectedGraph(num, g) {}
	pair<bool, vector<int>>toplogicalSort() {
		/*----------------------------------------------------------------------------------------------
		* 输入：有向图邻接矩阵
		* 输出：节点排序序列
		用顶点表示活动，用弧表示活动间的优先关系的有向图称为AOV网（Activity On Vertex Network)
		有向无环图(Directed Acyclic Graph,DAG)的拓扑排序步骤：
		1.定义一个队列Q并将所有入度为0的顶点入队
		2.取出队首的元素输出，删除以该顶点为起点的边，并且将连接该顶点的其他顶点的入度减一。
		   若某个顶点的入度减为0，那么就将改顶点加入到队列中。
		3.反复执行2操作直到队列为空，如果队列为空时如果队的结点数目恰好为N说明拓扑排序成功，
		   否则说明图中存在环
		----------------------------------------------------------------------------------------------*/
		vector<int>res;
		//初始化队列
		queue<int>Q;
		for (int i = 0; i < n; i++)
			if (!indegree[i])Q.push(i);
		//不断进行对0入度的点删除指向外的有向边
		while (Q.size())
		{
			int top = Q.front();
			Q.pop();
			res.emplace_back(top);
			for (int i = 0; i < n; i++)
				if (A[top][i]) {
					indegree[i] -= A[top][i];
					A[top][i] = 0;
					if (!indegree[i])Q.push(i);
				}
		}
		return { (res.size() == n),res };
	}
	static void _test() {
		ToplogicalSort
			g1(4, { {0,1},{0,2},{1,3},{2,3}, }),//输出：0,1,2,3
			g2(5, { {0,1},{1,2},{1,3},{4,1}, }),//输出：0,4,1,2,3
			g3(5, { {0,1},{1,2},{1,3},{4,1},{4,0} }),//输出：4,0,1,2,3
			g4(3, { {1,2} });//输出：0,1,2
		cout << g3;
		pair<bool, vector<int>>res = g3.toplogicalSort();
		if (res.first) cout << "拓扑排序成功!\n" << res.second;
		else cout << "图中存在环!\n";
	}
};

//关键路径
//AOE（Activity On Edge）网络
// 待补充

//主函数（用于测试）
int main()
{
	//MST::_test("kruskal");
	MinDist::_test_Dijkstra();
	MinDist::_test_Bellman_Ford();
	//MinDist::_test_Floyd();
	//Traversal::_test("dfs");
	//ToplogicalSort::_test();
	return 0;
}